

public class MySingleList {
    class ListNode {
        public int val;   //存储的数据
        public ListNode next;  //存的是下一个节点的位置

        public ListNode(int val) {  //new 一个节点的时候调用构造方法，由于不知道下一个节点是什么，所以不初始化next，默认为null
            this.val = val;
        }
    }

    public ListNode head;// 代表当前链表的头节点的引用

    //手动创建一个单链表
    public void createLink() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(45);
        ListNode listNode3 = new ListNode(23);
        ListNode listNode4 = new ListNode(90);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4; /* */
        head = listNode1;
    }

    /**
     * 遍历链表
     */
    public void display() {
        //如果说 把整个链表 遍历完成 那么 就需要 head == null
        // 如果说 你遍历到链表的尾巴  head.next == null
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //查找是否包含关键字key是否在单链表当中  (自己练习)
    public boolean contains2(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度 O(N)
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }


    //得到单链表的长度 O(N)   (自己练习)
    public int size2() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法 O(1)
    public void addFirst(int data) {
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;
    }

    //头插法 O(1)  （自己练习）
    public void addFirst2(int data) {
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;
    }

    //尾插法 O(N)    找尾巴的过程
    public void addLast(int data) {
        ListNode listNode = new ListNode(data);
        if (head == null) {
            head = listNode;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = listNode;
    }

    //尾插法 O(N)    找尾巴的过程 (自己练习)
    public void addLast2(int data) {
        ListNode listNode = new ListNode(data);
        if (head == null) {
            head = listNode;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        //走到这说明走到结尾点了
        cur.next = listNode;
    }

    //任意位置插入,假设第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        checkIndex(index);
        if (0 == index) {
            addFirst(data);
            return;
        }
        if (size() == index) {
            addFirst(data);
            return;
        }
        ListNode listNode = new ListNode(data);
        ListNode cur = findIndexSubOne(index);

        listNode.next = cur.next;
        cur.next = listNode;
    }

    /**
     * 找到 index-1位置的节点的地址
     *
     * @param index
     * @return
     */
    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //用于检查位置的合法性
    private void checkIndex(int index) throws ListIndexOutOfException {
        if (index < 0 || index > size()) {
            throw new ListIndexOutOfException("index位置不合法");
        }
    }


    /**
     * 找到关键字key的前一个节点
     *
     * @param key
     * @return
     */
    private ListNode searchPrev(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;//没有你要删除的节点
    }

    /**
     * 找到关键字key的前一个节点
     *
     * @param key
     * @return
     */
    private ListNode searchPrev2(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if (head == null) {
            return;
        }
        /*  注意不可以把while换成if ，因为有可能后面也是要删除的
        while(head.val == key) {
            head = head.next;
        }*/
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == key) {
            head = head.next;
        }
    }

    //删除所有值为key的节点   (自己练习)
    public void removeAllKey2(int key) {
        if (head == null) {
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        //走完判断头节点是不是要删除的
        if (head.val == key) {
            head = head.next;
        }
    }

    /**
     * 保证链表当中 所有的节点 都可以被回收，就是没有人引用的时候就会被回收
     */
    public void clear() {
        head = null;

        //StringBuilder sb = "fdfa";
    }

    //反转链表，力扣的 206题 简单题
    public ListNode reverseList() {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;

        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    //力扣876，返回链表中间节点 简单题目
    public ListNode middleNode() {
        /**
         * 这部分代码也可以不用写，下面的判断也适用于这种情况
         * if(head == null) {
         *             return null;
         *         }
         *         if (head.next == null) {
         *             return head;
         *         }
         */

        ListNode fastNode = head;
        ListNode slowNode = head;
        //利用快慢指针的思路，快指针走两步，慢指针走一步，那么快指针走完，慢指针就停在了中间的节点位置
        // (即是快指针速度是慢指针的2倍，时间相同，所以快指针走完，慢指针就在中间的节点位置)
        //注意需要加上fastNode != null 的条件，不然fastNode.next != null 会报空指针异常
        //注意，下面这两个条件的前后位置也不能换，不然fastNode.next != null 会报空指针异常
        while (fastNode != null && fastNode.next != null) {
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
        }
        return slowNode;
    }

    //力扣876，返回链表中间节点 简单题目
    public ListNode middleNode2() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        cur = head;
        for (int i = 0; i < count / 2; i++) {
            cur = cur.next;
        }
        return cur;
    }

    //牛客  找到链表中倒数第k个节点
    public ListNode findKthToTail(int k) {
        if (k <= 0 || head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        //1. fast走k-1步
        while (k - 1 != 0) {
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            k--;
        }
        //2、3、
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //牛客  找到链表中倒数第k个节点  (自己练习写的)
    public ListNode findKthToTail2(int k) {
        // 倒数第k个节点，fast和slow中间差了k - 1 步
        // 1. 先让fast走k - 1 步
        // 2. fast走完，开始和slow一起开始一步一步走
        // 3. fast走到最后一个节点停住，也就是 fast.next == null的时候，slow所停的位置就是倒数第k个节点
        // 画图更清晰
        if (head == null) {
            return null;
        }
        ListNode fastNode = head;
        ListNode slowNode = head;
        if (k == 0) return null;
        while (k - 1 > 0) {
            fastNode = fastNode.next;
            k--;
        }
        while (fastNode != null && fastNode.next != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        if (fastNode == null) return null;
        return slowNode;
    }

    //力扣21，合并两个有序数组
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(0);
        ListNode tmp = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tmp.next = list1;
                tmp = tmp.next;
                list1 = list1.next;
            } else {
                tmp.next = list2;
                tmp = tmp.next;
                list2 = list2.next;
            }
        }
        //走到这说明至少有一个不为空
        if (list1 != null) {
            tmp.next = list1;
        }
        if (list2 != null) {
            tmp.next = list2;
        }
        return newHead.next;
    }


    //牛客OR36  链表的回文结构  （字节笔试题）
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if (head == null) {
            return false;
        }
        //只有一个节点
        if (head.next == null) {
            return true;
        }
        // 1.找中间节点
        ListNode fastNode = head;
        ListNode slowNode = head;
        //利用快慢指针的思路，快指针走两步，慢指针走一步，那么快指针走完，慢指针就停在了中间的节点位置
        // (即是快指针速度是慢指针的2倍，时间相同，所以快指针走完，慢指针就在中间的节点位置)
        //注意需要加上fastNode != null 的条件，不然fastNode.next != null 会报空指针异常
        //注意，下面这两个条件的前后位置也不能换，不然fastNode.next != null 会报空指针异常
        while (fastNode != null && fastNode.next != null) {
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
        }
        // 2.进行翻转
        ListNode cur = slowNode.next;  //表示要反转的节点
        while (cur != null) {
            ListNode curNext = cur.next;  //用于记录cur的下一个节点，因为cur的next会变化，所以提前记录下位置
            cur.next = slowNode;
            slowNode = cur;
            cur = curNext;
        }

        // 3.head往后走，slow往前走，判断值是否相等
        while (head != slowNode) {
            if (head.val != slowNode.val) {
                return false;
            }
            // 这是判断偶数节点的情况
            if (head.next == slowNode) {
                return true;
            }
            head = head.next;
            slowNode = slowNode.next;
        }
        /**
         * 和上面while循环一样的效果
         while (head != slowNode) {
         if(head.val == slowNode.val) {
         // 这是判断偶数节点的情况
         if(head.next == slowNode) {
         return true;
         }
         head = head.next;
         slowNode = slowNode.next;
         }else {
         return false;
         }
         }
         */
        return true;
    }

    //力扣88.合并两个有序数组 简单题目
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //有一点利用归并排序的思想
        int i = m - 1;
        int j = n - 1;  //分别记录有效数据的最后一位
        int k = m + n - 1;  //记录nums1数组的最后一个位置
        while (i >= 0 && j >= 0) {
            if (nums1[i] <= nums2[j]) {
                nums1[k] = nums2[j];
                k--;
                j--;
            } else {
                nums1[k] = nums1[i];
                k--;
                i--;
            }
        }

        //走到这说明i 和 j有一个不为0   其中不用管1中的数据，因为本身就是有序的
        //只需要判断 数组2的情况就行,把数组2中的数据拷贝到数组1中去
        //即是有可能数组1走完了，数组2中还有数据
        while (j >= 0) {
            nums1[k] = nums2[j];
            k--;
            j--;
        }
    }

    //力扣26.删除有序数组中的重复项（简单题目）
    public int removeDuplicates(int[] nums) {
        if (nums == null) return 0;
        //定义两个指针，快指针去寻找不重复的元素，慢指针去找答案(即是要覆盖的地方)
        int fast = 1;
        int slow = 0;
        for (fast = 1; fast < nums.length; fast++) {
            if (nums[fast] == nums[slow]) {
                //fast++;
            } else {
                nums[slow + 1] = nums[fast];
                slow++;
                //fast++;
            }
        }
        return slow + 1;
    }

    //力扣26.删除有序数组中的重复项（简单题目）
    //用while循环来写
    public int removeDuplicates2(int[] nums) {
        if (nums == null) return 0;
        //定义两个指针，快指针去寻找不重复的元素，慢指针去找答案(即是要覆盖的地方)
        int fast = 1;
        int slow = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                nums[slow + 1] = nums[fast];
                slow++;
                fast++;
            } else {
                fast++;
            }
        }
        return slow + 1;
    }

    //牛客CM11，链表的分割（较难题目）
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if (pHead == null) {
            return null;
        }
        if (pHead.next == null) return pHead;

        // bs所在的节点链表是比x小的
        // as所在的节点链表是比x大的
        ListNode bs = null;  //代表前面节点
        ListNode be = null;   // be代替bs往后面走
        ListNode as = null;  //代表后面节点
        ListNode ae = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (bs == null) {  //代表前面节点为空
                    bs = cur;
                    be = cur;
                    cur = cur.next;
                } else {
                    be.next = cur;
                    be = cur;
                    cur = cur.next;
                }
            } else {
                if (as == null) {  //代表前面节点为空
                    as = cur;
                    ae = cur;
                    cur = cur.next;
                } else {
                    ae.next = cur;
                    ae = cur;
                    cur = cur.next;
                }
            }
        }
        //走完之后将前后节点进行连接起来
        /** be.next = as;
         ae.next = null;
         */
        //需要注意bs所在链表为空 ，或者后面节点as所在链表为空
        if (bs == null) {
            return as;
        } else {
            be.next = as;
            if (as != null) {
                ae.next = null;
            }
            return bs;
        }
    }

    //牛客CM11，链表的分割（较难题目）  (自己写的，方向不对，不够简洁)
    public ListNode partition2 (ListNode pHead,int x){
        // write code here
        if (pHead == null) {
            return null;
        }
        if (pHead.next == null) return pHead;
        ListNode NewHead = new ListNode(0);
        ListNode cur = NewHead;

        return null;
    }

    //力扣160：相交链表 （简单题目）
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.求两个链表的长度
        int lenA = 0;
        int lenB = 0;
        ListNode pl = headA;  //pl表示长的链表
        ListNode ps = headB;  //ps表示短的链表
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = lenA -lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB -lenA;
        }
        //走到这 pl永远指向最长的链表   ps永远指向短的链表

        // 2. 让长的先走len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        //要排序走到头还没有相交的情况
        if(pl == null) {
            return null;
        }
        return pl;  //上面那个if可以不写，若是pl为空，也是直接返回pl为空
    }


    //力扣：141. 判断是否有环，快指针走两步，慢指针走一步
    //一定是快指针走两步，慢指针走一步

    // 提问：快指针走三步，慢指针走一步行不行？  答：不行
    //   若是环内只有两个节点，相当于两步是一个周期，快指针走三步，一圈零一步，本质还是走一步，
    //   若是快指针在2节点，慢指针在1节点，则永远不能相遇

    // 提问：快指针走n步，慢指针走一步行不行？   答：不行
    //   若是环内只有 n - 1个节点，相当于n - 1 步是一个周期，快指针走n步，一圈零一步，本质还是走一步，
    //   若是快指针在2节点，慢指针在1节点，则永远不能相遇
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //假设有环的情况下
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {   //注： 相遇的地方不一定是刚入环时的节点
                return true;
            }
            //到这说明他俩相遇了，或者都是走到最后没有相遇是null
            /*if(fast == null) {
                return fasle;
            } */
        }
        return false;
    }

    //力扣142.返回有环链表中的环入口点 （中等）
    public ListNode detectCycle(ListNode head) {
        // 1.判断是否有环
        ListNode fast = head;
        ListNode slow = head;
        //假设有环的情况下
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {   //注： 相遇的地方不一定是刚入环时的节点
                //到这说明有环
                slow = head;
                while(fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                //走到这说明两者相等，此处就是入口点，为何是入口点，推导请看课件
                return fast;
            }
        }
        return null;
    }
}

